import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Created by zhourh on 2018/6/11.
 */
public class PascalTriangle {

    private static List<List<Integer>> cache = new ArrayList();

    static {
        List<Integer> row1 = new ArrayList<>();
        row1.add(1);
        cache.add(row1);
    }

    public static String integerArrayListToString(List<Integer> nums, int length) {
        if (length == 0) {
            return "[]";
        }

        String result = "";
        for(int index = 0; index < length; index++) {
            Integer number = nums.get(index);
            result += Integer.toString(number) + ", ";
        }
        return "[" + result.substring(0, result.length() - 2) + "]";
    }

    public static String integerArrayListToString(List<Integer> nums) {
        return integerArrayListToString(nums, nums.size());
    }

    public static String int2dListToString(List<List<Integer>> nums) {
        StringBuilder sb = new StringBuilder("[");
        for (List<Integer> list: nums) {
            sb.append(integerArrayListToString(list));
            sb.append(",");
        }

        sb.setCharAt(sb.length() - 1, ']');
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(int2dListToString(new PascalTriangle().generate(5)));
    }

    public List<List<Integer>> generate(int numRows) {
        if (numRows < 1) {
            return Collections.emptyList();
        }

        if (cache.size() >= numRows) {
            return cache.subList(0, numRows);
        }

        for (int row = cache.size(); row < numRows; row++ ) {
            List<Integer> rowList = new ArrayList<>();
            for (int i = 0; i <= row; i++) {
                int left = i > 0 ? cache.get(row - 1).get(i - 1) : 0;
                int right = i < row ? cache.get(row - 1).get(i) : 0;
                rowList.add(i, left + right);
            }

            cache.add(row, rowList);
        }

        return generate(numRows);
    }
}
